long long Solve(int n, int m, vector<int>& weights){

    int max_weight = 0;
    for(auto it: weights){
        max_weight = max(max_weight, it);
    }
    int min_k = max_weight;
    int max_k = ceil(float n/m)*max_weight;
    int may_k;
    while(min_k < max_k){
        int curr_k = (min_k + max_k)/2;
        int temp_m = m;
        int last_k = 0;
        for(auto it: weights){
            if(last_k >= it){
                last_k -= it;
            }
            else{
                if(temp_m > 0){
                    temp_m --;
                    last_k = curr_k;
                }
                else{
                    temp_m--;
                    break;
                }
            }
        }
        if(temp_m < 0){
            min_k = curr_k+1;
        }
        else if(temp_m > 0){
            max_k = curr_k-1;
        }
        else{
            may_k = curr_k;
            max_k = curr_k-1;  
        }
    }
    return may_k;
}